package norepeat

// stores last occurred pos + 1; 0 means not seen
var lastOccurred = make([]int, 0xffff) // 记录每个字母最后出现的位置
// 最长不含有重复字符的子串
func LengthOfNonRepeatingSubStr(s string) int { //  200	   5910338 ns/op
	for i := range lastOccurred { // 5670324  ns/op
		lastOccurred[i] = 0
	}
	start := 0
	maxLength := 0

	for i, ch := range []rune(s) {
		if lastI := lastOccurred[ch]; lastI >= start {
			start = lastI
		}
		if i-start+1 > maxLength {
			maxLength = i - start + 1
		}
		lastOccurred[ch] = i + 1
	}

	return maxLength
}

func lengthOfNonRepeatingSubStr2(s string) int {
	lastOccurred := make(map[rune]int) // 记录每个字母最后出现的位置
	start := 0
	maxLength := 0

	for i, ch := range []rune(s) {
		if lastI, ok := lastOccurred[ch]; ok && lastI >= start {
			start = lastI + 1
		}
		if i-start+1 > maxLength {
			maxLength = i - start + 1
		}
		lastOccurred[ch] = i
	}

	return maxLength
}
